package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/4 12:11
 * @DESCRIPTION
 */
// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
public class 电话号码的字母组合 {
    //自己写出
    List<List<Character>>mapping=new ArrayList<>();//数字和字母的映射
    StringBuilder path=new StringBuilder();//其中一个路径结果
    List<String> res=new ArrayList<>();//最终结果
    //树的深度是 digits的长度
    //树的广度是 每个按键所能表示的字母个数
    public List<String> method1(String digits) {
        char[] chars = digits.toCharArray();
        if (chars.length==0)return res;
        mapping.add(Arrays.asList('a','b','c'));
        mapping.add(Arrays.asList('d','e','f'));
        mapping.add(Arrays.asList('g','h','i'));
        mapping.add(Arrays.asList('j','k','l'));
        mapping.add(Arrays.asList('m','n','o'));
        mapping.add(Arrays.asList('p','q','r','s'));
        mapping.add(Arrays.asList('t','u','v'));
        mapping.add(Arrays.asList('w','x','y','z'));
        recursion(0,chars);
        return res;
    }
    //index：表示到digits的第index+1个数
    public void recursion(int index,char[] digits){
        if(index==digits.length){
            res.add(path.toString());
            return;
        }
        List<Character> characters = mapping.get((digits[index]-'0')-2);//取出数组和字母映射
        for (int i = 0; i < characters.size(); i++) {
            path.append(characters.get(i));
            recursion(index+1,digits);
            path.deleteCharAt(path.length()-1);//删除最后一个字符
        }
    }

    public List<String> practice(String digits) {
        char[] chars = digits.toCharArray();
        if (chars.length==0)return res;
        mapping.add(Arrays.asList('a','b','c'));
        mapping.add(Arrays.asList('d','e','f'));
        mapping.add(Arrays.asList('g','h','i'));
        mapping.add(Arrays.asList('j','k','l'));
        mapping.add(Arrays.asList('m','n','o'));
        mapping.add(Arrays.asList('p','q','r','s'));
        mapping.add(Arrays.asList('t','u','v'));
        mapping.add(Arrays.asList('w','x','y','z'));
        recursionPractice(0,chars);
        return res;
    }

    private void recursionPractice(int i, char[] chars) {
        if(i>=chars.length){
            res.add(path.toString());
            return;
        }
        for (int j = 0; j < mapping.get(chars[i]-'0'-2).size(); j++) {
            path.append( mapping.get(chars[i]-'0'-2).get(j));
            recursionPractice(i+1,chars);
            path.deleteCharAt(path.length()-1);
        }
    }

    public List<String> practice2(String digits) {
        if(digits.length()==0){
            return new ArrayList<>();
        }
        mapping.add(Arrays.asList('a','b','c'));
        mapping.add(Arrays.asList('d', 'e', 'f'));
        mapping.add(Arrays.asList('g', 'h', 'i'));
        mapping.add(Arrays.asList('j', 'k', 'l'));
        mapping.add(Arrays.asList('m', 'n', 'o'));
        mapping.add(Arrays.asList('p', 'q', 'r', 's'));
        mapping.add(Arrays.asList('t', 'u', 'v'));
        mapping.add(Arrays.asList('w', 'x', 'y', 'z'));
        recursionPractice2(digits,0);
        return res;
    }
    public void recursionPractice2(String digits,int startIndex){
        if(startIndex>=digits.length()){
            res.add(path.toString());
            return;
        }
        List<Character> characters = mapping.get(digits.charAt(startIndex)-'0' - 2);
        for (char c:characters) {
            path.append(c);
            recursionPractice2(digits,startIndex+1);
            path.deleteCharAt(path.length()-1);
        }
    }
}
